home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / TwoDTSP.m < prev    next >
Encoding:
Text File  |  1992-08-18  |  5.7 KB  |  204 lines
  1.  
  2. #import "TwoDView.h" /* the main class */
  3. #import "TwoDTSP.h"
  4. #import "prototypes.h"
  5.  
  6.  
  7. float simpleTSP(TwoDView *s,float *data,float *distances,int *edges,int n);
  8. #define STATUS(s) [self->statusText setStringValue: s];
  9.  
  10. #define FROM 0
  11. #define TO 1
  12. static float *distances=0,optimalValue=0; /* file scopr vars */
  13. @implementation TwoDView(TSP)
  14.  
  15. - doSimpleNearNeighbor
  16. {
  17.  
  18.     if(distances != NULL)
  19.     NX_FREE(distances);
  20.  
  21.     /* calculate distances */
  22.     NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
  23.     STATUS("Calculating distances");
  24.     CalculateDistance(data,distances,numPoints);
  25.     /* spaces for edges is allocated in TwoDView in InitGeomerty */
  26.     optimalValue = simpleTSP(self,data,distances,tsp_edges,numPoints);
  27.     [optimalValueField setFloatValue: optimalValue at: 0];
  28.  
  29.     [optimizeButton setEnabled: YES];    
  30.     return self ;
  31. }
  32. - doCheapestInsertion
  33. {
  34.     if(distances != NULL)
  35.     NX_FREE(distances);
  36.  
  37.     /* calculate distances */
  38.     NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
  39.     STATUS("Calculating distances");
  40.     CalculateDistance(data,distances,numPoints);
  41.     /* spaces for edges is allocated in TwoDView in InitGeomerty */
  42.     optimalValue = CheapestInsertion(self,data,distances,tsp_edges,numPoints);
  43.     [optimalValueField setFloatValue: optimalValue at: 0];
  44.     //NX_FREE(distances);
  45.     [optimizeButton setEnabled: YES];    
  46.  
  47.     return self ;
  48. }
  49. /*--------------------------------------------------------------------
  50. Near Neighbor TSP
  51.  
  52.                                             Mary Tork Roth/1991-Nov-30
  53. --------------------------------------------------------------------*/
  54. - doNearestNeighbor
  55. {
  56.     if(distances != NULL)
  57.     NX_FREE(distances);
  58.  
  59.     /* calculate distances */
  60.     NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
  61.     STATUS("Calculating distances");
  62.     CalculateDistance(data,distances,numPoints);
  63.     /* spaces for edges is allocated in TwoDView in InitGeomerty */
  64.     optimalValue = NearestNeighbor(self,data,distances,tsp_edges,numPoints);
  65.     [optimalValueField setFloatValue: optimalValue at: 0];
  66.     //NX_FREE(distances);
  67.     [optimizeButton setEnabled: YES];
  68.     return self ;
  69.  
  70. }
  71. /* nearest addition */
  72. - doNearestAddition
  73. {
  74.     if(distances != NULL)
  75.     NX_FREE(distances);
  76.  
  77.     /* calculate distances */
  78.     NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
  79.     STATUS("Calculating distances");
  80.     CalculateDistance(data,distances,numPoints);
  81.     /* spaces for edges is allocated in TwoDView in InitGeomerty */
  82.     optimalValue = NearestAddition(self,data,distances,tsp_edges,numPoints);
  83.     [optimalValueField setFloatValue: optimalValue at: 0];
  84.     //NX_FREE(distances);
  85.     [optimizeButton setEnabled: YES];    
  86.     return self ;
  87.  
  88. }
  89. - doFarthestInsertion
  90. {
  91.     if(distances != NULL)
  92.     NX_FREE(distances);
  93.  
  94.     /* calculate distances */
  95.     NX_MALLOC(distances,float,numPoints*(numPoints-1)/2);
  96.     STATUS("Calculating distances");
  97.     CalculateDistance(data,distances,numPoints);
  98.     /* spaces for edges is allocated in TwoDView in InitGeomerty */
  99.     optimalValue = FarthestInsertion(self,data,distances,tsp_edges,numPoints);
  100.     [optimalValueField setFloatValue: optimalValue at: 0];
  101.     [optimizeButton setEnabled: YES];    
  102.     return self ;
  103.  
  104. }
  105.  
  106. /*--------------------------------------------------------------------
  107. Called from within drawSelf:.
  108. Assume that scaling has been setup, 
  109. This could be a general drawing routine for TSPs
  110.                                                  Bill Roth/1991-Nov-18
  111. --------------------------------------------------------------------*/
  112.  
  113. - drawTSP
  114. {
  115.     int x,from,to;
  116. #ifdef DEBUG
  117.     printf("inDrawTSP");
  118. #endif
  119.  
  120.     for(x=0;x<numPoints;x++) {
  121.     from = tsp_edges[x*2 + FROM];
  122.     to=  tsp_edges[x*2 + TO];
  123.     if (from >= 0 && from < numPoints && to >= 0 && to < numPoints) {
  124.         PSnewpath();
  125.         PSmoveto(X(from),Y(from));
  126.         PSlineto(X(to),Y(to));
  127.         PSstroke();
  128.         NXPing();
  129.     }
  130.     }
  131.     return self ;
  132. }
  133. /*--------------------------------------------------------------------
  134. Gets the time from the slider and sets the field to its value.
  135.  
  136.                                                  Bill Roth/1991-Dec-01
  137. --------------------------------------------------------------------*/
  138.  
  139. - timeValue:sender
  140. {
  141.     drawTime = [sender intValue];
  142.     [timeField setIntValue: drawTime at: 0];
  143.     return self ;
  144. }
  145. /* optimize the edges that exist.
  146. */
  147.  - Optimize
  148.  {
  149.      
  150.      optimalValue = TourOptimization(self,data,distances,tsp_edges,
  151.                      optimalValue,numPoints);
  152.      [optimalValueField setFloatValue: optimalValue at: 0];
  153.      [optimizeButton setEnabled: NO];    
  154.      [self display];
  155.      return self;
  156.     
  157.  }
  158. /*--------------------------------------------------------------------
  159. End of ObjC section
  160.  
  161.                                                  Bill Roth/1991-Dec-01
  162. --------------------------------------------------------------------*/
  163.  
  164.  
  165. #define FROM 0
  166. #define TO 1
  167. /* everything is allocated before it comes in */
  168. extern kfrom(int l,int m,int n);
  169.  
  170. float simpleTSP(TwoDView *self,float *data,float *distances,int *edges,int n)
  171. {
  172.      int x,i;
  173.      float opt;
  174.      char m[80];
  175.  
  176.      opt =0.0;
  177.      for(x=0;x<n-1;x++) {/* calculate the distances*/
  178.      sprintf(m,"Doing edge %d",x);
  179.      [self->statusText setStringValue:m];
  180.      opt += distances[kfrom(x,x+1,n)];
  181.      edges[x*2 + FROM] = x; /* connect the first one to the 2nd one ...*/
  182.      edges[x*2 + TO] = x+1;
  183.      PSnewinstance();
  184.      for(i=0;i<=x;i++) {
  185.          [self drawEdge:X(i):Y(i):X(i+1):Y(i+1)];
  186.          NXPing();
  187.     }
  188.      [self->optimalValueField setFloatValue: opt at: 0];
  189.      usleep(self->drawTime);
  190.      }
  191.      edges[(n-1)*2+FROM] = n-1;
  192.      edges[(n-1)*2+TO] = 0;
  193.      opt += distances[kfrom(0,(n-1),n)];
  194.         PSnewinstance();
  195.     for(i=0;i<n-1;i++) {
  196.          [self drawEdge:X(i):Y(i):X(i+1):Y(i+1)];
  197.     }
  198.      [self drawEdge:X(n-2):Y(n-2):X(0):Y(0)];// connect to the beginning
  199.      NXPing();
  200.      return opt;
  201.  }
  202.  
  203. @end
  204.